import java.util.Scanner;

/**
 * @Author Created by xqq
 * @Date Created in 11:51 2017/6/19
 */
public class KaTa_1 {
    public static void main(String args[]) {
        float value[] = {12, 25, 4, 5, 8, 85, 7, 6, 2, 1};
        int values[] = {12, 25, 4, 5, 8, 85, 7, 6, 2, 1};
        // input(value);//输入数值
        //哼哼！！！
        // A:求和方案
        // theSum(value);
        // B:获取两个数中的较大值
        // getExtremum(value);
        //   C:比较两个数据是否相同

        // D:排序
        //bubbleSort(value);//1.冒泡排序
        //sort(values,0,value.length-1);//2.快排
        // selectSort(values);//3.选择排序
        shellSort(values);//4.希尔排序
        // E:输出m行n列的星形

        // F:输出nn乘法表
    }

    /**
     * @Author：season
     * @Description: 求和
     * @Date: 2017/6/19 11:57
     */
    private static void theSum(float value[]) {

        float result = 0;
        if (value.length > 0) {
            for (int i = 0; i < value.length; i++) {
                result += value[i];
            }
            System.out.println("结果为：" + result);
        }

    }

    /**
     * @Author：season
     * @Description:取最大值
     * @Date: 2017/6/19 14:48
     */
    public static void getExtremum(float value[]) {
        bubbleSort(value);
        System.out.println("最大值" + value[value.length - 1]);
        System.out.println("最小值" + value[0]);
    }

    /**
     * @Author：season
     * @Description: 输入工具
     * @Date: 2017/6/19 14:56
     */
    public static float[] input(float value[]) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入要计操作的值(上限十个值)：");
        for (int i = 0; i < 10; i++) {
            value[i] = sc.nextFloat();
        }
        return value;
    }

    /**
     * @Author：season
     * @Description:冒泡排序 　/**
     * 冒泡排序
     * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
     * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
     * 针对所有的元素重复以上的步骤，除了最后一个。
     * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
     * 需要排序的整型数组
     * @Date: 2017/6/19 15:04
     */
    public static float[] bubbleSort(float value[]) {
        float box;
        if (value.length > 0) {
            for (int i = 0; i < value.length - 1; i++) {
                for (int j = 0; j < value.length - 1 - i; j++) {
                    if (value[j] > value[j + 1]) {
                        box = value[j];
                        value[j] = value[j + 1];
                        value[j + 1] = box;
                    }
                }
            }
            System.out.println("排序结果为：");
            for (int i = 0; i < value.length; i++) {
                System.out.print(value[i]);
            }
        }
        return value;
    }
    /**
     * @Author：season
     * @Description:快速排序
     * @Date: 2017/6/19 16:11
     */
    /**不可行方案，未实现*/
    /**
     * @Author：season
     * @Description:获取中间值
     * @Date: 2017/6/20 10:17
     */

  /*  public static int getMiddle(float value[]) {
        int middle = 0;
        int low; //开始位置
        int high; //终止位置
        if (value.length > 0) {
            //for (int i =0;i<value.length;i++){
            low = 0;
            high = value.length - 1;
            float p = value[low];
            for (int j = 0; j < value.length; j++) {
                if (value[low] > value[high]) {
                    float box = value[low];
                    value[low] = value[high];
                    value[high] = box;

                }
                if (value[low] == p) {
                    high--;
                } else {
                    low++;
                }

                // }

            }
            middle = low;
            System.out.println("排序结果为：");
            for (int i = 0; i < value.length; i++) {
                System.out.print(value[i]);
            }
        }
        return middle;
    }
*/
    /**
     * @Author：season
     * @Description:
     * @Date: 2017/6/20 10:26
     */
  /*  public static int getMiddles(float value[],float number){
        int middle = 0;
        for (int i=0; i<value.length;i++){
            if (value[i]==number){
                middle = i;
            }
        }
        return middle;
    }
    public static void quickSort(float[] value) {
        int index = 0 ;
        float middle = value[index];
        index = getMiddle(value);
        if (index != 0) {
            float valueO[] = new float[value.length - index-1]; //分割成小数组
            for (int x = 0; x < value.length - index-1; x++) {
                valueO[x] = value[index+1+x];
            }

            float valueT[] = new float[value.length - (value.length - index-1)]; //分割成小数组
            for (int y = 0; y < value.length - (value.length - index)-1; y++) {
                valueT[y] = value[y];
            }
            float valueS[] = new float[valueO.length+valueT.length]; //合并数组
            for (int i = 0;i<valueS.length;i++){
                for (int x = 0;x<valueO.length;x++){
                    valueS[x] = valueO[x];
                }
                for (int y = 0;y<valueO.length;y++){
                    valueS[valueO.length-1+y] = valueT[y];
                }
            }
        }
    }*/
    /**不可行方案，未实现*/
    /**
     * 可行方案，网上摘抄 BEGIN
     */
    public static int partition(int[] array, int lo, int hi) {
        //固定的切分方式
        int key = array[lo];
        while (lo < hi) {
            while (array[hi] >= key && hi > lo) {//从后半部分向前扫描
                hi--;
            }
            array[lo] = array[hi];
            while (array[lo] <= key && hi > lo) {//从前半部分向后扫描
                lo++;
            }
            array[hi] = array[lo];
        }
        array[hi] = key;
        return hi;
    }

    public static void sort(int[] array, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int index = partition(array, lo, hi);
        sort(array, lo, index - 1);
        sort(array, index + 1, hi);
        System.out.println("排序结果为：");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
        }
    }
    /**可行方案，网上摘抄 END*/
    /**
     * @Author：season
     * @Description:选择排序
     * @Date: 2017/6/21 10:29
     */
    public static int[] selectSort(int values[]) {
        for (int i = 0; i < values.length; i++) {
            for (int y = i; y < values.length; y++) {
                if (values[i] > values[y]) {
                    int box = values[i];
                    values[i] = values[y];
                    values[y] = box;
                }
            }
        }
        System.out.println("排序结果为：");
        for (int i = 0; i < values.length; i++) {
            System.out.print(values[i] + ",");
        }
        return values;
    }
    /**
     * @Author：season
     * @Description:希尔排序  未实现
     * @Date: 2017/6/21 13:36
     */
    public static void shellSort(int values[]) {
       /* int length = values.length;
           divisionArray(values,5);
        System.out.println("排序结果为：");
        for (int i = 0; i < values.length; i++) {
            System.out.print(values[i]+",");
        }
        divisionArray(values,3);
        System.out.println("排序结果为：");
        for (int i = 0; i < values.length; i++) {
            System.out.print(values[i]+",");
        }
        divisionArray(values,2);
        System.out.println("排序结果为：");
        for (int i = 0; i < values.length; i++) {
            System.out.print(values[i]+",");
        }
        divisionArray(values,1);
        System.out.println("排序结果为：");
        for (int i = 0; i < values.length; i++) {
            System.out.print(values[i]+",");
        }

        return values;
*/
        int a[] = {1, 54, 6, 3, 78, 34, 12, 45, 56, 100};
        double d1 = a.length;
        int temp = 0;

        while (true) {
            d1 = Math.ceil(d1 / 2);
            int d = (int) d1;
            for (int x = 0; x < d; x++) {

                for (int i = x + d; i < a.length; i += d) {
                    int j = i - d;
                    temp = a[i];
                    for (; j >= 0 && temp < a[j]; j -= d) {
                        a[j + d] = a[j];
                    }
                    a[j + d] = temp;
                }
            }
            if (d == 1) {
                break;
            }
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i]);
            }
            System.out.println();
        }
   /* public static int[] divisionArray(int values[],int d){
         for (int i = 0; i<values.length-d+1;i++){
            if (values[i]>values[i+d-1]){
                int box = values[i];
                values[i] = values[i+d-1];
                values[i+d-1] = box;
            }
         }
         return values;
    }*/
    }
}
